package algorithm7.leetcode.dfs_and_bfs;

import java.util.LinkedList;
import java.util.Queue;

public class LC200_241018 {


/*

200. 岛屿数量
中等

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。


示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

 */

    public static void main(String[] args) {
        char[][] grid_01 = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}};
        char[][] grid_02 = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}};

        Dfs dfs = new Dfs();
        Bfs bfs = new Bfs();
//        int islands_01 = dfs.numIslands(grid_01);
//        System.out.println("islands_01 = " + islands_01);
//        int islands_02 = dfs.numIslands(grid_02);
//        System.out.println("islands_02 = " + islands_02);

        int islands_01_bfs = bfs.numIslands(grid_01);
        System.out.println("islands_01_bfs = " + islands_01_bfs);
        int islands_02_bfs = bfs.numIslands(grid_02);
        System.out.println("islands_02_bfs = " + islands_02_bfs);
    }

    private static class Dfs {
        /*
            遍历grid，遇到1，岛屿数量+1；并进行dfs，将当前位置相邻的位置都置为0（上下左右）
         */
        private int numIslands(char[][] grid) {
            int ans = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    if (grid[i][j] == '1') {
                        ans++;
                        dfs(grid, i, j);
                    }
                }
            }
            return ans;
        }

        private void dfs(char[][] grid, int i, int j) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == '0') {
                // 越界返回
                return;
            }
            // 当前位置置为0
            grid[i][j] = '0';
            // 上
            dfs(grid, i - 1, j);
            // 下
            dfs(grid, i + 1, j);
            // 左
            dfs(grid, i, j - 1);
            // 右
            dfs(grid, i, j + 1);
        }

    }

    private static class Bfs {
        /*
            遍历grid，遇到1，岛屿数量+1；并进行dfs，将当前位置相邻的位置都置为0（上下左右）
         */
        private int numIslands(char[][] grid) {
            int ans = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    if (grid[i][j] == '1') {
                        ans++;
                        grid[i][j] = '0';
                        bfs(grid, i, j);
                    }
                }
            }
            return ans;
        }

        private void bfs(char[][] grid, int i, int j) {
            Queue<Position> queue = new LinkedList<>();
            queue.add(new Position(i, j));
            while (!queue.isEmpty()) {
                Position cur = queue.poll();
                int curRow = cur.row;
                int curCol = cur.col;
                // 上
                if (curRow - 1 >= 0 && grid[curRow - 1][curCol] == '1') {
                    queue.add(new Position(curRow - 1, curCol));
                    grid[curRow - 1][curCol] = '0';
                }
                // 下
                if (curRow + 1 < grid.length && grid[curRow + 1][curCol] == '1') {
                    queue.add(new Position(curRow + 1, curCol));
                    grid[curRow + 1][curCol] = '0';
                }
                // 左
                if (curCol - 1 >= 0 && grid[curRow][curCol - 1] == '1') {
                    queue.add(new Position(curRow, curCol - 1));
                    grid[curRow][curCol - 1] = '0';
                }
                // 右
                if (curCol + 1 < grid[curRow].length && grid[curRow][curCol + 1] == '1') {
                    queue.add(new Position(curRow, curCol + 1));
                    grid[curRow][curCol + 1] = '0';
                }
            }
        }

        private static class Position {
            public int row;
            public int col;

            public Position(int row, int col) {
                this.row = row;
                this.col = col;
            }
        }
    }

    private static class Uf {
        /*
            并查集
         */
        private int numIslands(char[][] grid) {
            return 0;
        }

    }


}
